package java111_2;

import java.util.*;

public class Day39 {
    //https://ac.nowcoder.com/acm/problem/205832
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = "";
        while(in.hasNext()){
            s += in.next();
        }
        int[] arr = new int[27];
        int max = 0;
        char res = '0';
        for(int i = 0; i < s.length(); i++){
            int index;
            if(s.charAt(i) == ' '){
                index = 26;
            } else {
                index = s.charAt(i) - 'a';
            }
            if(++arr[index] > max){
                max = arr[index];
                res = s.charAt(i);
            }
        }
        System.out.println(res);
    }


    //https://www.nowcoder.com/practice/c471efdbd33a4a979539a91170c9f1cb?tpId=128&tqId=33774&ru=/exam/oj
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.next();
            HashMap<Character, Integer> hashMap = new HashMap<>();
            for(int i = 0; i < s.length(); i++){
                hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
            }
            Collection<Integer> list = hashMap.values();
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for(Integer i : list){
                heap.offer(i);
            }
            int res = 0;
            while(heap.size() != 1){
                int num1 = heap.poll();
                int num2 = heap.poll();
                heap.offer(num1 + num2);
                res += num1 + num2;
            }
            System.out.println(res);
        }
    }


    //https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04?tpId=230&tqId=40431&ru=/exam/oj
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] dp = new int[n][n+1];
        for (int i = 1; i <= n; i++) {
            dp[0][i] = -1;
        }
        // dp[i][j] 表示 从前 i 个数中挑选，总和恰好为 j 时，最少挑出来的个数
        for(int i = 1; i <= Math.sqrt(n); i++){
            for(int j = 0; j <= n; j++){
                if(j - i*i >= 0) {
                    if(dp[i-1][j] == -1) {
                        dp[i][j] = dp[i][j - i * i] + 1;
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - i * i] + 1);
                    }
                } else {
                    dp[i][j] = dp[i-1][j] == -1 ? 0 : dp[i-1][j];
                }
            }
        }
        System.out.println(dp[(int)Math.sqrt(n)][n]);
    }
    public static void main02(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] dp = new int[n+1][n+1];
        // dp[i][j] 表示从前 i 个数中选完全平方数 和恰好为 j 的最少个数  return dp[sqrt(n)][n];
        for(int i = 1; i <= n; i++){
            dp[0][i] = 10001;
        }
        int m = (int)Math.sqrt(n);
        for(int i = 1; i <= m; i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = dp[i-1][j];
                if(j - i*i >= 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-i*i] + 1);
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}
